package www.study.com;

import java.util.ArrayList;
import java.util.List;

//全排列 https://leetcode.cn/problems/permutations/
public class code46 {
    public static void main(String[] args) {

    }
    class Solution {
        List<List<Integer>> res = new ArrayList<>();
        boolean[] vis; //vis[i]代表第i个数被访问过
        int[] numIn;

        //方式二 - 速度更优
        public List<List<Integer>> permute(int[] nums) {
            numIn = nums;
            vis = new boolean[numIn.length];
            List<Integer> list = new ArrayList<>();
            dfs(list);
            return res;
        }

        public void dfs(List<Integer> list){
            if(list.size() == numIn.length){
                res.add(new ArrayList<>(list));
                return;
            }
            for(int i = 0 ; i < numIn.length ; i++){
                if(vis[i]) continue;
                vis[i] = true;
                list.add(numIn[i]);
                dfs(list);
                list.remove(list.size() - 1);
                vis[i] = false;
            }
        }

        //方式一
        // public List<List<Integer>> permute(int[] nums) {
        //     List<List<Integer>> res = new ArrayList<>();
        //     func(res,nums,0);
        //     return res;
        // }
        // public void func(List<List<Integer>> res,int[] nums,int i){
        //     if(i == nums.length - 1){
        //         //List<Integer> list = new ArrayList<>(Arrays.asList(nums));
        //         List<Integer> list = Arrays.stream(nums).boxed().collect(Collectors.toList());
        //         res.add(list);
        //         return;
        //     }
        //     for(int k = i ; k < nums.length ; k++){
        //         swap(nums,i,k);
        //         func(res,nums,i + 1); //这里注意，递归进入下一层，必须是i+1，不要写成func(res,nums,k)
        //         swap(nums,i,k);
        //     }
        // }
        // public void swap(int[] nums,int i,int j){
        //     int tmp = nums[i];
        //     nums[i] = nums[j];
        //     nums[j] = tmp;
        // }
    }
}
